L2-045 堆宝塔

题目 L2-045 堆宝塔

思路分析

• 初始用 A柱 放第一块，准备两个栈 a, b。
• 对于当前圈 C：
  • 若 C < a.top()，放到 A。
  • 否则，如果 B 为空或 C > b.top()，放到 B。
  • 否则，视为 A 上的塔完成（ans[cnt] = A 的一整个塔），计数器 cnt++，并清空 A；
    • 然后把 B 中比 C 大的一个个放到 A 上；
    • 最后把 C 放到 A。
• 最后：
  • 把当前 A 作为一座塔收下；
  • 把剩余的 B 依次放入新的塔中（反向插入）。

代码实现

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

using ll = long long;

using ull = unsigned long long;

using PII = pair<int,int>;

using Pll = pair<ll,ll>;

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

const int inf = 0x3f3f3f3f;

vector<int> nums;

int main(){

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int n;cin>>n;

	nums.resize(n);

	for(int i=0;i<n;i++){

		cin>>nums[i];

	}

	stack<int> a,b;

	vector<deque<int>> towers;

	for(int i=0;i<n;i++){

		int c=nums[i];

		if(a.empty() || a.top()>c)	a.push(c);

		else if(b.empty() || c>b.top())	b.push(c);

		else{

			deque<int> tmp;

			while(!a.empty()){

				tmp.push_front(a.top());

				a.pop();

			}

			towers.push_back(tmp);

			while(!b.empty() && b.top()>c){

				a.push(b.top());

				b.pop();

			}

			a.push(c);

		}

	}

	if(!a.empty()){

		deque<int> tmp;

		while(!a.empty()){

			tmp.push_front(a.top());

			a.pop();

		}

		towers.push_back(tmp);

	}

	if(!b.empty()){

		deque<int> tmp;

		while(!b.empty()){

			tmp.push_front(b.top());

			b.pop();

		}

		towers.push_back(tmp);

	}

	int tower_cnt=towers.size();

	int max_height=-inf;

	for(auto d:towers){

		int curs=d.size();

		max_height=max(max_height,curs);

	}

	cout << tower_cnt << " " << max_height << endl;

	return 0;

}

同类题型

视频讲解

⬅️ L2-044 大众情人 🏠 00-天梯赛 ➡️ L2-046 天梯赛的赛场安排